COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00011 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a39.tex[154,phy] \today\hfill}

\bigskip
\line{\bf The Relation Between Stacks and Parentheses\hfil}

Let $\Sigma$ be an alphabet, $\Sigma↑{\ast}$ the strings over~$\Sigma$.
All strings can be formed by starting with~$\epsilon$ and appending
characters on one end. We assume it's the right end, but all the results
that follow work for the left end as well. We use $S↓a(x)$, where
$a\in\Sigma$, $x\in\Sigma↑{\ast}$, to mean the string~$x$ with character~$a$
appended. The following are the {\sl Peano axioms\/} for~$\Sigma↑{\ast}$:

\disleft 20pt:(1):
$\epsilon\in\Sigma↑{\ast}$.

\disleft 20pt:(2):
If $x\in\Sigma↑{\ast}$ and $a\in\Sigma$, then $S↓a(x)\in\Sigma↑{\ast}$.

\disleft 20pt:(3):
If $\epsilon$ has a property, and that property is preserved when a
character of~$\Sigma$ is appended to a string, then every string 
in~$\Sigma↑{\ast}$ has the property. In a formula,
$$\bigl(P(\epsilon)\wedge((\forall x\in\Sigma↑{\ast},a\in\Sigma)
P(x)⊃P(S↓a(x)))\bigr)⊃(\forall x\in\Sigma↑{\ast})P(x)\,.$$

\disleft 20pt:(4):
$S↓a(x)≠\epsilon$.

\disleft 20pt:(5):
$S↓a(x)=S↓b(y)$ only if $a=b$, $x=y$.

\proclaim Theorem. Every string in $\Sigma↑{\ast}$ is either $\epsilon$
or $S↓a(x)$ for some~$a$ and~$x$.

\noindent{\bf Proof.} Let $P(y)$ be the property $y=\epsilon\vee
(\exists x,a)y=S↓a(x)$. An easy application of axiom~3 shows that
$y\in\Sigma↑{\ast}⊃P(y)$.

\medskip
Concatenation is defined by

\disleft 20pt:(1):
$x\otimes\epsilon =x$.

\disleft 20pt:(2):
$x\otimes S↓a(y)=S↓a(x\otimes y)$.

{\narrower\smallskip\rmn\noindent
{\bf Drill \#1.} Use the Peano axioms to show that the above define $x\otimes y$
for all~$x$ and~$y$.
\smallskip}

{\narrower\smallskip\rmn\noindent
{\bf Drill \#2.} Use the Peano axioms to show $\epsilon\otimes x=x$ and
$(x\otimes y)\otimes z=x\otimes (y\otimes z)$.
\smallskip}

A stack is a string; a stack with alphabet $\Sigma$ is a string in~$\Sigma↑{\ast}$.
Let the relation $\{\,\langle x,S↓a(x)\rangle\mid$\break 
$x\in\Sigma↑{\ast}\,\}$ be
called push~$a$, and the converse relation pop~$a$.

{\narrower\smallskip\rmn\noindent
{\bf Drill \#3.} Show push $a$ is a function.
\smallskip}

{\narrower\smallskip\rmn\noindent
{\bf Drill \#4.} Show pop $a$ is a partial function, defined on~$u$ iff
$u=S↓a(v)$ for some~$v$.
\smallskip}

{\narrower\smallskip\rmn\noindent
{\bf Drill \#5.} Show ${\rm push}\;a\,\circ\,{\rm pop}\; a=I↓{\Sigma↑{\ast}}$.
\smallskip}

{\narrower\smallskip\rmn\noindent
{\bf Drill \#6.} Show ${\rm push}\;a\,\circ\,{\rm pop}\; b=\emptyset$ if $b≠a$.
\smallskip}

Define a language $L$ of nested parentheses by:

\disleft 20pt:(1):
$\epsilon\in L$.

\disleft 20pt:(2):
If $x\in L$, so are $(x)$ and $[x]$.

\disleft 20pt:(3):
If $x,y\in L$, so is $xy$.

\disleft 20pt:(4):
That's all. In other words, (1), (2), and (3) allow proofs by induction
about~$L$.

Define a CFG $G↓1$ with productions
$$E→\epsilon\mid(E)E\mid [E]E\,.$$

{\narrower\smallskip\rmn\noindent
{\bf Drill \#7.} Prove by induction $L=L↓{G↓1}$.
\smallskip}

We shall call this language $L↓{(\,)[\,]}$. If we substitute push~$a$ for~$($,
pop~$a$ for~$)$, push~$b$ for~$[$, and pop~$b$ for~$]$ in the above grammar~$G↓1$,
we get the grammar~$G↓2$:
$$F→\epsilon\mid\;{\rm push}\; a\,F\;{\rm pop}\; a\,F\mid\,{\rm push}\;
b\,F\;{\rm pop}\; b\,F\,.$$

{\narrower\smallskip\rmn\noindent
{\bf Drill \#8.} Prove by induction every sentence in $L↓{G↓2}$ names
a relation equal to $I↓{\Sigma↑{\ast}}$. (By convention, $\epsilon$
names~$I↓{\Sigma}$.)
\smallskip}

{\narrower\smallskip\rmn\noindent
{\bf Drill \#9.} Show that any sequence of pushes and pops that changes the empty
stack to the empty stack is a sentence in the above grammar.
\smallskip}

In other words, the sequence of stack operations in a standardized
PDM computation is an (encoded) string in $L↓{(\,)[\,]}$.

{\narrower\smallskip\rmn\noindent
{\bf Drill \#10.} Take a labeled graph form of a standardized PDM. 
Prove that a string is a computation of that PDM if and only if:
\smallskip}

\display 40pt:{\rmn (1)}:
{\rmn It is a labeled path through the graph.}

\display 40pt:{\rmn (2)}:
{\rmn Omitting all symbols except push $a$, pop $a$, push $b$, pop $b$ gives
a sentence in~$G↓2$.}

\smallskip
\display 20pt::
{\rmn
(The labeled graph form labels each arc with operations like read~$a$,
write~$b$, push~$c$, pop~$d$, etc. A~labeled path is 
$q↓0l↓1q↓1l↓2q↓2\ldots$, where $q↓{i-1}l↓iq↓i$ is a labeled arc
of the graph.)
}

{\narrower\smallskip\rmn\noindent
{\bf Drill \#11.} Show that if $M$ is a PDM, there is a GSM, $M'$, such that
the set of computations of~$M$ is the image of $L↓{(\,)[\,]}$ under 
transductions by~$M'$; that is, if~$M'$ has input-output relation~$R$,
the set of computations of~$M$ is $L↓{(\,)[\,]}\circ R$.
\smallskip}

{\narrower\smallskip\rmn\noindent
{\bf Drill \#12.} Show that the set of strings accepted by a PDM is the image of
$L↓{(\,)[\,]}$ under transductions by a~GSM (a~GSM mapping).
\smallskip}

\proclaim Theorem. The CFLs are the images of $L↓{(\,)[\,]}$ under GSM mappings.

\bigskip
\parindent0pt
\copyright 1986 Robert W. Floyd.
First draft (not published)
May 2, 1986.
%revised date;
%subsequently revised.

\bye